package com.cty.fourteenthDay;

import java.util.Arrays;
import java.util.Map;

/*
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * */
public class Q_17 {
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        int ans = firstMissingPositive(nums);
        System.out.println(ans);
    }

    // 力扣官方题解 思路:先判断数组中是否含有1 不含有 返回1 含有 将所有 大于n(数组长度)的数变为1 小于等于0的数变为1 (结果会出现在[1,n+1]这个区间内) 如果出现了这个范围内的值 将这个值 - 1 的索引上的数变为负数即可
    public static int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        int n = nums.length;
        boolean flag = false;
        for (int num : nums) {
            if (num == 1) {
                flag = true;
            }
        }
        if (!flag) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = 1;
            }
        }
        // 将该值作为数组下标 将该位置的元素变为负数
        for (int i = 0; i < n; i++) {
            int index = Math.abs(nums[i]) - 1;
            nums[index] = -Math.abs(nums[index]);
        }
        // 找出大于0的值 说明该索引值 + 1 是缺少的整数直接返回
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // 若没有找到正值 说明缺少的是 n + 1
        return n + 1;
    }
}
